package main.java.indi.zyj.sword;

import java.util.Arrays;
import java.util.HashMap;

public class VerifyTreeOrder {

    HashMap<Integer, Integer> map = new HashMap<>();
    public boolean verifyTreeOrder(int[] postorder) {
        int n = postorder.length;
        if(n == 0)return true;
        int[] inOrder = Arrays.copyOf(postorder, n);
        Arrays.sort(inOrder);
        //存储每个值的下标，与后序进行比较
        for(int i = 0; i < n; ++i){
            map.put(inOrder[i], i);
        }
        return isBinTree(postorder, inOrder, 0, n - 1, 0, n - 1);
    }

    boolean isBinTree(int[] postorder, int[] inOrder, int l1, int r1, int l2, int r2){
        if(l1 > r1)return true;
        int index = map.get(postorder[r1]);
        if(index < l2 || index > r2)return false;
        return isBinTree(postorder, inOrder, l1, l1 + (index - 1 - l2), l2, index - 1) && isBinTree(postorder, inOrder,  l1 + (index - 1 - l2) + 1, r1 - 1, index + 1, r2);

    }

}
